Tun Teja Nenda kepada Sultan Mahmud Syah telah jatuh gering dan mangkat sewaktu Portugis mula menyerang Melaka yang pada ketika itu Sultan Mahmud Syah dan orang-orang kerajaan Melaka berundur ke Muar, pada tahun 1511. Tun Teja telah dimakamkan di perkampungannya di Merlimau, sekitar 24 km daripada bandar Melaka.

Berbeza dengan versi Hikayat Hang Tuah yang menyebut tentang Hang Tuah yang telah difitnah oleh orang-orang istana Melaka dan telah membawa diri ke Pahang setelah dinasihati oleh Bendahara Paduka Raja. Sesampai di Pahang, Hang Tuah telah membuat perhubungan dengan Bendahara Seri Buana iaitu ayahanda kepada Tun Teja dan Tun Jenal, adinda Tun Teja. Pada mulanya Tun Teja menolak akan pelawaan perhubungan dengan Hang Tuah namun setelah diberi ubat guna-guna melalui Dang Ratna, inang pengasuh Tun Teja yang juga menjadi ibu angkat Hang Tuah, Tun Teja telah jatuh cinta kepada pahlawan itu, walhal Tun Teja Telah pun bertunang dengan Megat Panji Alam, anak raja Terengganu.

Hang Tuah telah membuat pakatan untuk membawa Tun Teja ke Melaka melalui jalan laut, walau pun pada mulanya orang-orang Pahang berjaya menghidu akan tindakan Hang Tuah, diketuai oleh Tun Jenal. Namun angkatan tentera Pahang terpaksa berpatah balik setelah tiang kapal mereka patah dipanah oleh Hang Tuah. Sesampai di Melaka, Tun Teja diarak dengan gajah ke balairung seri istana Melaka. Tun Teja terperanjat kerana dipersembahkan kepada Sultan Mansur Syah, walhal kedatangannya ke Melaka adalah untuk mengahwini Hang Tuah. Namun setelah diberi sirih jampi oleh Hang Tuah, Tun Teja melupakan Hang Tuah dan akhirnya mengahwini Sultan Melaka, manakala Hang Tuah telah diampuni oleh Sultan Melaka dan dijadikan Laksamana.

Megat Panji Alam yang amat marah dengan kejadian yang menimpa tunangannya, telah mengambil keputusan untuk menyerang Melaka bersama 4000 tentera namun beliau singgah di Pahang untuk mengadap Sultan Pahang. Namun beliau dibunuh oleh Hang Jebat dan Hang Kasturi yang telah diarahkan oleh Hang Tuah yang telah dapat menghidu tindakan Megat Panji Alam. Sultan Pahang yang murka kerana gagal menjalinkan hubungan dengan Terengganu, telah menjatuhkan hukuman bunuh terhadap keluarga Tun Teja.